/**
 * [29] 两数相除
 *
 * @format
 * @lc app=leetcode.cn id=29 lang=javascript
 */

// @lc code=start
/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
// 指数自增的辗转相减
var divide = function (dividend, divisor) {
    // 32 位有符号整数取值范围
    const [INT_MIN, INT_MAX] = [-(2 ** 31), 2 ** 31 - 1]
    // 范围限制：使数据严格属于 [INT_MIN, INT_MAX] 超出范围取边界值
    const numLimited = num => (num < INT_MIN ? INT_MIN : num > INT_MAX ? INT_MAX : num)
    // 结果（商）符号：同号为正，异号为负（异或为 true）
    const SING = (dividend > 0) ^ (divisor > 0)
    // 取绝对值
    ;[dividend, divisor] = [Math.abs(dividend), Math.abs(divisor)]
    // 记录商的绝对值
    let count = 0
    while (dividend >= divisor) {
        // 步长与除数，自翻倍
        let [step, temp] = [1, divisor]
        while (dividend >= temp) {
            // 被除数辗转减，辗转次数累加
            dividend -= temp
            count += step
            // 除数与步长翻倍
            temp += temp
            step += step
            // 用位运算会超时
            // temp = temp << 1
            // step = step << 1
        }
    }
    return numLimited(SING ? -count : count)
}

/* // 暴力算法（辗转相减）：除法是减法的高阶运算
var divide = function (dividend, divisor) {
    // 同号减除数，异号加除数
    // + +, + -, - +, - -
    const FLAG = (dividend > 0) ^ (divisor > 0)
    const isContinue = (dividend, divisor) => Math.abs(dividend) >= Math.abs(divisor)
    let [count, step, backup] = [0, 1, divisor]
    while (isContinue(dividend, divisor)) {
        if (FLAG) {
            dividend += divisor
            count--
        } else {
            dividend -= divisor
            count++
        }
    }
    return count
} */
// debugger
// let [dividend, divisor] = [10, 3]
// let result = divide(dividend, divisor)
// console.log(result)
// @lc code=end
